package com.yinxin.wudasuanfa.sort;

import com.yinxin.wudasuanfa.sort.until.PrintArr;

/**
 * @author yinxin
 * @version 1.0
 * @Description: 归并排序
 * @date 2022/4/1810:53
 */

public class mergeSort {
    public static void main(String[] args) {
        int[] arr = {9,5,2,7,12,4,3,1,11};
        int n = 9;
        System.out.print("排序前：");
        PrintArr.printArr(arr);
        mergeSort(arr,n);
        System.out.print("排序后：");
        PrintArr.printArr(arr);
    }
    //归并排序入口
    static void mergeSort(int[] arr, int n) {
        //分配一个辅助数组
        int[] tmp = new int[n];
        //归并排序
        msort(arr, tmp, 0, n - 1);
    }

    //归并排序
    private static void msort(int[] arr, int[] tmp, int left, int right) {
        //只有一个元素就不需要划分
        //只有一个元素的区域，本身就是有序的，需要被归并
        if (left < right) {
            //中间点
            int mid = (left + right) / 2;
            //递归划分左半区
            msort(arr, tmp, left, mid);
            //递归划分右半区
            msort(arr, tmp, mid + 1, right);
            //合并已经排序的部分
            merge(arr,tmp,left,mid,right);
        }
    }

    //合并
    private static void merge(int[] arr,int[] tmp,int left,int mid,int right){
        //标记左半区第一个未排序的元素
        int lpos= left;
        //标记右半区第一个未排序的元素
        int rpos = mid+1;
        //临时数组元素下标
        int pos= left;
        //合并(左半区有元素并且右半区有元素)
        while (lpos<=mid && rpos<=right){
            if(arr[lpos]<arr[rpos]){//左半区第一个元素更小
                tmp[pos++]=arr[lpos++];
            }else {//右半区第一个元素更小
                tmp[pos++]=arr[rpos++];
            }
        }
        //合并左半区剩余元素
        while (lpos<=mid){
            tmp[pos++]=arr[lpos++];
        }
        //合并右半区剩余元素
        while (rpos<=right){
            tmp[pos++]=arr[rpos++];
        }
        //把临时数组中合并后的元素复制回原来的数组
        while (left<=right){
            arr[left]=tmp[left];
            left++;
        }
    }

}
